package ans.p42;

/**
 * #      42
 * 名称   接雨水
 * 链接   https://leetcode-cn.com/problems/trapping-rain-water
 * 题解   [1831](https://leetcode-cn.com/problems/trapping-rain-water/solution)
 * 通过率 55.1%
 * 难道   困难
 */

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }


    public int trap2(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            int min = Math.min(leftMax, rightMax);
            if (height[left] <= min) {
                ans += min - height[left];
                System.out.print("[" + left + "|" + (min - height[left]) + "] ");
                left++;
            } else if (height[right] <= min && right > left) {
                ans += min - height[right];
                System.out.print("[" + right + "|" + (min - height[right]) + "] ");
                right--;
            } else {
                right--;
                left++;
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().trap(new int[]{0, 1, 2, 0, 3, 0, 1, 2, 0, 0, 4, 2, 1, 2, 5, 0, 1, 2, 0, 2}));
//
//
//        System.out.println(new Solution().trap(new int[]{4, 2, 3}));
//        System.out.println(new Solution().trap(new int[]{4, 2, 0, 3, 2, 5}));
//        System.out.println(new Solution().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}